"""
问题描述

　主串为′ababcabcacbab′
，模式串为′abcac′
，现在要求模式串在主串中出现的位置。
"""
def index(S, T):
    """
    :type S: str
    :type T: str
    :rtype: int
    暴力求解
    """
    i = 0
    j = 0
    while i < len(S) and j < len(T):
        if S[i] == T[j]:    # 依次比较，相等则比较下一个字符
            i += 1
            j += 1
        else:    # 如果不相等，指针i需要回溯到上个起点的下一个位置
                 # 并从头开始比较
            i -= j - 1
            j = 0
    # while循环结束后，要么是找到合适匹配了，要么是遍历完主串都没有找到合适匹配
    if j == len(T):
        return i - j
    else:
        return -1


def get_next(T):
    i = 0
    j = -1
    next_val = [-1] * len(T)
    while i < len(T)-1:
        if j == -1 or T[i] == T[j]:
            i += 1
            j += 1
            # next_val[i] = j
            if i < len(T) and T[i] != T[j]:
                next_val[i] = j
            else:
                next_val[i] = next_val[j]
        else:
            j = next_val[j]
    return next_val


class Solution:
    # 获取next数组

    # KMP算法
    def kmp(self, S, T):
        i = 0
        j = 0
        next = get_next(T)
        while i < len(S) and j < len(T):
            if j == -1 or S[i] == T[j]:
                i += 1
                j += 1
            else:
                j = next[j]
        if j == len(T):
            return i - j
        else:
            return -1
##https://www.zhihu.com/question/21923021
# brute force
def brute_force(s,p):
    for i in range(len(s)-len(p)+1):
        if s[i:i+len(p)] == p:
            return i

def next(p):
    nxt = []
    nxt.append(0)
    x = 1
    now = 0
    while x < len(p):
        if p[now] ==p[x]:
            now +=1
            x+=1
            nxt.append(now)
        elif now:
            now = nxt[now-1]
        else:
            nxt.append(0)
            x +=1
    return nxt

def search(s,p):
    tar = 0
    pos = 0
    nxt = next(p)
    res = 0
    while tar < len(s):
        if s[tar] == p[pos]:
            tar +=1
            pos +=1
        elif pos:
            pos = nxt[pos-1]
        else:
            tar +=1
        if pos == len(p):
            res = tar-pos +1
            pos = nxt[pos-1]
    return res



if __name__ == '__main__':

    haystack = 'acabaabaabcacaabc'
    needle = 'abaabcac'

    s = Solution()
    # print(next(needle))
    print(search(haystack, needle))    # 输出 "5"